1. Field of Invention
The present invention relates to data compression systems. More particularly, the present invention relates to loss-less data compression and a method and means for increasing the speed of compressing a stream of data in systems that employ a dictionary to store string codes.
2. Description of the Prior Art
Heretofore, loss-less data compression algorithms were known. Some of the best known data compressions systems and methods are referred to as Lempel Ziv One (LZ-1) Lempel Ziv Two (LZ-2) and Lempel Ziv Welch (LZW). All of these adaptive loss-less data compression systems employ a dictionary for storing string codes that are indicative of strings of data and symbols or characters encountered in an input data stream. Once a string is identified it is stored as a code having fewer bits than the identified string of data so that subsequent occurrences of the same string in the data stream are replaced with the previously stored string code. All three above-mentioned data compression systems involve searching plural locations in the dictionary to determine if a string code has been previously stored for the string under examination. The process involves matching a sequence of input data characters with the same sequence already encoded in a dictionary location.
To minimize the time required for searching plural locations in the dictionary, it has been suggested that a hashing algorithm be used to perform the matching function. Hash searches compute an index in a table based on the data being sought. The efficiency of the hash table search is determined by the organization of the table and whether multiple items can hash to the same area of the table without conflict. Hashing systems suffer from high costs of implementations and complex computations which result in performance reducing overhead. One LZW hashing method is described in U.S. Pat. No. 4,558,302 which is incorporated by reference herein.
It has also been suggested that binary searches could be employed in which the memory and portions of the memory are divided and searched sequentially until a match or no match is found. Binary searches by definition require multiple searches in the dictionary and also require table reordering, but have the advantage that they reduce the overhead incurred in the complex calculations associated with hashing.
It has been suggested that a content addressable memory (CAM) or associative memory be employed to reduce the number of comparisons of the contents of plural strings located in the dictionary. This system is efficient, yet complex and it can be very costly. An example of this method is described in U.S. Pat. No. 5,838,264 which is incorporated by reference herein.
It would be desirable to provide a method and apparatus that completely avoids plural searches in data compression systems that employ string dictionaries. It is further desirable that the output from the new data compression system be formatable to be compatible with existing data compression systems such as LZW so that the existing decompressor/decoders would be able to receive and decode compressed data without any modification.